package Study1;

public class Study17 {

    //合并两个有序链表
    /*
    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
    * */
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    /*class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            // 创建一个新的链表，通过尾插法，
            // 遍历两个链表，把小于的节点插入到新的链表中去
            // 率先为空的拼接后面的节点
            ListNode newHead = new ListNode(-1); // 创建一个新的节点
            ListNode cur = newHead;

            while(null != list1 && null != list2) {
                if(list1.val < list2.val) {  //  list1.val的数值小，插入
                    cur.next = list1;
                    cur = cur.next;
                    list1 = list1.next;
                } else {                      // list2.val 的数值
                    cur.next = list2;
                    cur = cur.next;
                    list2 = list2.next;
                }

            }

            // list1 率先为空，拼接 list2
            if(null == list1) {
                cur.next = list2;
            }
            // list2 率先为空，拼接 list1
            if(null == list2) {
                cur.next = list1;
            }

            return newHead.next; // 返回新链表的第二个节点，因为第二个节点才存放着两个链表插入的数值

        }
    }*/




    // 160. 相交链表
    /*
  给你两个单链表的头节点 headA 和 headB ，
  请你找出并返回两个单链表相交的起始节点。
 如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    * */

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
   /* public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            // 首先 计算两个链表的长度，求出其差值，
            // 通过差值，让长的先走，
            // 走到同一位置后，同速度一起，地址相同即为相交点
            if(null == headA || null == headB) {
                return null;
            }


            ListNode pa = headA;
            ListNode pb = headB;


            int lenA = 0;
            int lenB = 0;
            int len = 0;

            // 求headA链表的长度
            while(null != pa) {
                pa = pa.next;
                lenA ++;
            }

            // 求headB链表的长度
            while(null != pb) {
                pb = pb.next;
                lenB++;
            }

            len = lenA - lenB;

            pa = headA; // 重新指向各自对应的头节点
            pb = headB;

            // 判断那个单链表更长，先走，
            if(len > 0) {
                for(int i = 0; i < len; i++) {
                    pa = pa.next;
                }
            } else {
                len = lenB - lenA;
                for(int i = 0; i < len; i++) {
                    pb = pb.next;
                }
            }

            // 同步出发，相遇即为相交点，不相遇，没有相交点
            while(null != pb && null != pa && pa != pb) {
                pa = pa.next;
                pb = pb.next;
            }
            // 跳出循环判断，其结果相等，还是为空的
            if(null != pa && pa == pb) {
                return pa;
            } else {
                return null;
            }




        }
    }*/





    // 环形链表 II
    /*
    给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    * */
    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
   /* public class Solution {
        public ListNode detectCycle(ListNode head) {
            // 2倍速，相遇，不相遇不是环
            // 在第一次相遇的位置，一头，一尾同速度，再次相遇的节点就是，入环位置
            ListNode falst = head;
            ListNode slow = head;
            if(null == head) { // 链表不为空
                return null;
            }

            // 2倍速，移动相遇，第一次相遇
            while(null != falst && null != falst.next) {
                falst = falst.next.next; //
                slow = slow.next;

                if(slow == falst) { // 第一次相遇的节点位置
                    break;
                }
            }
            // 跳出循环判断是否为，空，
            if(null == falst || null == falst.next) {
                return null;
            }

            // 第一次相遇点开始，和头开始，再次相遇即为 入环点
            while(head != falst) {
                falst = falst.next;
                head = head.next;
            }

            return falst;

        }
    }*/





    // 环形链表
    /*给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    * */
//    import java.util.*;

    /*
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }*/
   /* public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            // write code here
            if(null == A || null == A.next) {
                return true;
            }
            ListNode falst = A;
            ListNode slow = A;

            // 1.找到中间节点,2倍速，3倍速，4倍速也可以但是，
            // 相遇的概率小，容易错开，2倍速是最佳的
            while(null != falst && null != falst.next) {
                // 不可以交换顺序，防止对 falst.next的空引用，
                // 以及短路存在的细节，falst == null,为假，后面的不执行，就不会有对空的引用了
                // 使用你 falst.next  ，falst.next.next 容易忽略falst
                falst = falst.next.next;
                slow = slow.next;
            }

            // 反转链表
            ListNode nextSlow = slow.next;
            while(null != nextSlow) { // 注意这里是 slow.next 不为空的引用
                ListNode nextSlow2 = nextSlow.next;
                nextSlow.next = slow;
                slow = nextSlow;
                nextSlow = nextSlow2;
            }

            while(A != slow) {
                if( A.val != slow.val) {
                    return false;
                }

                if(slow != A.next) {
                    return true;
                }
                A = A.next;
                slow = slow.next;
            }

            return true;
        }
    }*/






    // 面试题:链表的回文结构
    /*
    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900
    * */
//    import java.util.*;

    /*
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }*/
   /* public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            // write code here
            if(null == A || null == A.next) {
                return true;
            }
            ListNode falst = A;
            ListNode slow = A;

            // 1.找到中间节点,2倍速
            while(null != falst && null != falst.next) {
                // 不可以交换顺序，防止对 falst.next的空引用，
                // 以及短路存在的细节，falst == null,为假，后面的不执行，就不会有对空的引用了
                // 使用你 falst.next  ，falst.next.next 容易忽略falst
                falst = falst.next.next;
                slow = slow.next;
            }

            // 反转链表
            ListNode nextSlow = slow.next;
            while(null != nextSlow) { // 注意这里是 slow.next 不为空的引用
                ListNode nextSlow2 = nextSlow.next;
                nextSlow.next = slow;
                slow = nextSlow;
                nextSlow = nextSlow2;
            }

            while(A != slow) {
                if( A.val != slow.val) {
                    return false;
                }

                if(slow != A.next) {
                    return true;
                }
                A = A.next;
                slow = slow.next;
            }

            return true;
        }
    }*/
}
